package leetcode_800;

/**
 *@author 周杨
 *RotatedDigits_788_ 给定一个正整数表示区间[0-N] 问这个区间有多少数 旋转180度是合法数字 且不是自身
 *describe:用动态规划记录状态 很巧妙的解法 AC 57%
 *2018年10月22日 下午1:58:00
 */
public class RotatedDigits_788_ {
	public int rotatedDigits(int N) {
        int[] dp = new int[N + 1];
        //dp0表示无效 dp1表示反转后仍然有效 dp2表示反转后不同
        int count = 0;
        for(int i = 0; i <= N; i++){
            if(i < 10){//初始化
                if(i == 0 || i == 1 || i == 8) dp[i] = 1;
                else if(i == 2 || i == 5 || i == 6 || i == 9){
                    dp[i] = 2;
                    count++;
                }
            } else {
                int a = dp[i / 10], b = dp[i % 10];//拆分
                if(a == 1 && b == 1) dp[i] = 1;//反转后不变 则不加分 但是会保留
                else if(a >= 1 && b >= 1){//至少有一个可以反转后变化
                    dp[i] = 2;//由此可见 dp不是1就是2
                    count++;
                }
            }
        }
        return count;
    }
}
